package leetcode_周赛._2022._202206;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/6/19 11:09
 * 298 场力扣周赛
 */
public class _19 {

    /**
     * 5218. 个位数字为 K 的整数之和
     * 算法：完全背包
     *
     * @param num num
     * @param k   k
     * @return int
     */
    public int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        if (k > num) return -1;
        List<Integer> nums = new ArrayList<>();
        int tmp = k, x = 1;
        while (tmp < num) {
            nums.add(tmp);
            tmp = x * 10 + k;
            ++x;
        }
        int[] dp = new int[num + 1];
        Arrays.fill(dp, num + 1);
        dp[0] = 0;
        for (int i = 1; i <= num; i++) {
            for (Integer n : nums) {
                if (i >= n && dp[i - n] != num) dp[i] = Math.min(dp[i], dp[i - n] + 1);
            }
        }
        if (dp[num] == num + 1) return -1;
        return dp[num];
    }

    // 数学 + 枚举
    public int minimumNumbersPerfect(int num, int k) {
        if (num == 0) return 0;
        for (int i = 1; i <= num; i++) {
            int t = num - i * k;
            if (t >= 0 && t % 10 == 0) return i;
        }
        return -1;
    }

    /**
     * 6099. 小于等于 K 的最长二进制子序列
     * 跟最长上升子序列差不多
     * 算法：动态规划
     */
    static long[] ns = new long[31];

    static {
        int tmp = 1;
        for (int i = 0; i <= 30; i++) {
            ns[i] = tmp;
            tmp *= 2;
        }
    }

    public int longestSubsequence(String s, int k) {
        int len = s.length();
        int[] dp = new int[len];
        long[] nums = new long[len];
        Arrays.fill(dp, 1);
        nums[len - 1] = s.charAt(len - 1) == '0' ? 0 : 1;
        for (int i = len - 2; i >= 0; i--) {
            int num = s.charAt(i) - '0';
            for (int j = len - 1; j > i; j--) {
                long tmp = nums[j];
                if (num != 0) {
                    if (dp[j] > 30) continue;
                    tmp += ns[dp[j]];
                }
                if (tmp <= k && (dp[j] + 1) > dp[i]) {
                    dp[i] = dp[j] + 1;
                    nums[i] = tmp;
                }
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) ans = Math.max(ans, dp[i]);
        return ans;
    }

}
